package com.lwl.Algorithmic_data_structure.快排.mycode;

import java.util.Stack;

/**
 * 快速排序的非递归版本（迭代，dfs）
 */
public class QuickSortLoop {

    static class PartitionIndex
    {
        int leftSide;
        int rightSide;

        public PartitionIndex(int leftSide, int rightSide) {
            this.leftSide = leftSide;
            this.rightSide = rightSide;
        }
    }


    public static void quickSortLoop(int[] array)
    {
        if (array == null || array.length <= 1)
        {
            return;
        }

        int startPartitionIndex = (int)(Math.random() * array.length - 1);

        Partition.swap(array,startPartitionIndex,array.length - 1);

        int[] equalArea = Partition.partition(array, 0, array.length - 1);

        Stack<PartitionIndex> stack = new Stack<>();
        stack.push(new PartitionIndex(0,equalArea[0] - 1));
        stack.push(new PartitionIndex(equalArea[1] + 1,array.length - 1));
        //接下来相当于深搜了
        while (!stack.isEmpty())
        {
            PartitionIndex pi = stack.pop();
            if (pi.leftSide < pi.rightSide)
            {
                Partition.swap(array,pi.leftSide + (int)(Math.random() * (pi.rightSide - pi.leftSide + 1)),pi.rightSide);
                int[] eqArea = Partition.partition(array, pi.leftSide, pi.rightSide);
                stack.push(new PartitionIndex(pi.leftSide,eqArea[0] - 1));
                stack.push(new PartitionIndex(eqArea[1] + 1,pi.rightSide));
            }
        }
    }
}
